package mf.trees.binary;

import java.io.File;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Arrays;
import mf.tools.Command;
import mf.trees.Rule;
import mf.trees.SLTreeGrammar;

@SuppressWarnings("unchecked")
/**
 * TreeModel. Represents the tree grammar defined by File <b>f</b> and
 * the mappings L and R.
 * 
 * @author Maik Funkat
 */
public class TreeModel {
	
	//debug mode displays more informations
	private boolean DEBUG_MODE = false;
	
	//Tree grammar
	private SLTreeGrammar gr;
	
	//Stack for traversing the tree
	private Deque<Command> T = new ArrayDeque<Command>();

	//ArrayLists for left derivations
	private ArrayList<Integer> L[];
	//ArrayLists for right derivations
	private ArrayList<Integer> R[];

	//starting variable
	private int S = 0;

	//current node
	private String currentNode = "0";

	/** Construct a new tree model. */
	public TreeModel(File f, boolean d) {
		DEBUG_MODE = d;
		
		//load grammar file
		gr = new SLTreeGrammar(f);
		
		if(d)
			System.out.println(
				"Loading file " + f.getAbsolutePath() + "\n" +
				"Rules:\n" + gr.toString()
			);
		
		//initialize mappings
		L = new ArrayList[gr.size()];
		R = new ArrayList[gr.size()];
		
		//preprocess derivation maps
		preprocessDerivationMaps();
				
		//initialize stack
		T.push(new Command(S, H(S), Command.LEFT_DIRECTION));
		T.push(new Command(L(S, H(S)), 0, Command.UP_DIRECTION));
	}

	/** Calculate mappings L and R. */
	public void preprocessDerivationMaps() {
		//in the first run, we save the direct descendants
		for(int i=0; i<gr.size(); i++) {
			Rule r = gr.getRule(i);

			ArrayList<Integer> L_i = new ArrayList<Integer>();
			ArrayList<Integer> R_i = new ArrayList<Integer>();

			//if the current rule is of type 1
			if(!r.isType2()) {
				L_i.add(r.child(0));
				R_i.add(r.child(1));
			}

			L[i] = L_i;
			R[i] = R_i;
		}

		//in the second run, we collect all left and right derivations
		for(int i=0; i<gr.size(); i++) {
			if(L[i].size() != 0) {
				ArrayList<Integer> tmp = L[L[i].get(0).intValue()];
				
				while(true) {
					if(tmp.size() == 0)
						break;

					L[i].add(tmp.get(0));
					tmp = L[tmp.get(0)];
				}
			}
			if(R[i].size() != 0) {
				ArrayList<Integer> tmp = R[R[i].get(0).intValue()];
				
				while(true) {
					if(tmp.size() == 0)
						break;

					R[i].add(tmp.get(0));
					tmp = R[tmp.get(0)];
				}
			}
		}
		
		if(DEBUG_MODE)
			System.out.println("preprocess mappings...\n"+
				"L = "+Arrays.toString(L)+"\n"+
				"R = "+Arrays.toString(R)+"\n"
		);
	}
	
	/** Navigate to the left child of the current node. */
	public void gotoLeftChild() {
		Command top = T.peek();
		Rule rule = gr.getRule(top.variable());
		
		//if the rule has the form A -> a
		if(rule.childs() == 0) {
			return;
		}
				
		//if the rule has the form A -> f(B, x), we follow B
		if(rule.child(0).intValue() > 0) {
			Integer B = rule.child(0);
			Integer k = H(B);
			
			//add maximal left chain starting at B (can be zero) and one up-step
			if(k.intValue() > -1) {
				T.push(new Command(B, k, Command.LEFT_DIRECTION));
				T.push(new Command(L(B, k.intValue()), 0, Command.UP_DIRECTION));
			} else
				T.push(new Command(B, 0, Command.UP_DIRECTION));
			
			currentNode += ".1";
			return;
		}
		
		//if the rule has the form A -> f(x, B), we must find x 
		if(rule.child(0).intValue() == 0) {
			//delete U-step
			T.pop();
			
			//delete possible right chains
			if(T.peek().direction().intValue() == Command.RIGHT_DIRECTION)
				T.pop();
			
			//next stack element must be of form (A, i, L)
			Command lChain = T.pop();
			Integer X_v = lChain.variable(), ell = 0;
			
			//if i > 0, reduce length of left chain by 1
			if(lChain.length().intValue() > 0) {
				T.push(new Command(lChain.variable(), lChain.length()-1, lChain.direction()));
				
				X_v = L(lChain.variable(), lChain.length()-1);
			} else {  //look for preceding right chain
				if(!T.isEmpty()) {
					if(T.peek().direction().intValue() == Command.RIGHT_DIRECTION) {
						Command rChain = T.pop();
					
						X_v = rChain.variable();
						ell = rChain.length() + 1;
					}
				}
			}
			
			//done one right step
			T.push(new Command(X_v, ell, Command.RIGHT_DIRECTION));
			
			//do maximal left step (can be zero) and one up step
			X_v = R(X_v, ell);
			Integer k = H(X_v);
			
			//maximal left step plus up step
			if(k.intValue() > -1) {
				T.push(new Command(X_v, k, Command.LEFT_DIRECTION));
				T.push(new Command(L(X_v, k.intValue()), 0, Command.UP_DIRECTION));
			} else  //just one up step
				T.push(new Command(X_v, 0, Command.UP_DIRECTION));
			
			currentNode += ".1";
			return;
		}
	}

	/** Navigate to the right child of the current node. */
	public void gotoRightChild() {
		Command top = T.peek();
		Rule rule = gr.getRule(top.variable());
		
		//if the rule has the form A -> a
		if(rule.childs() == 0) {
			return;
		}
		
		//if the rule has the form A -> f(x, B), we follow B
		if(rule.child(1).intValue() > 0) {
			//preorder is incremented by the size of x, so we have to find it
			
			
			Integer B = rule.child(1);
			Integer k = H(B);
			
			//add maximal left chain starting at B (can be zero) and one up-step
			if(k.intValue() > -1) {
				T.push(new Command(B, k, Command.LEFT_DIRECTION));
				T.push(new Command(L(B, k.intValue()), 0, Command.UP_DIRECTION));
			} else
				T.push(new Command(B, 0, Command.UP_DIRECTION));
			
			currentNode += ".2";
			return;
		}
		
		//if the rule has the form A -> f(B, x), we must find x
		if(rule.child(1).intValue() == 0) {
			//delete U-step
			T.pop();
			
			//delete possible right chains
			if(T.peek().direction().intValue() == Command.RIGHT_DIRECTION)
				T.pop();
			
			//next stack element must be of form (A, i, L)
			Command lChain = T.pop();
			Integer Y = lChain.variable(), ell = 0;
			
			//if i > 0, reduce length of left chain by 1
			if(lChain.length().intValue() > 0) {
				T.push(new Command(lChain.variable(), lChain.length()-1, lChain.direction()));
				
				Y = L(lChain.variable(), lChain.length()-1);
			} else {  //look for preceding right chain
				if(!T.isEmpty()) {
					if(T.peek().direction().intValue() == Command.RIGHT_DIRECTION) {
						Command rChain = T.pop();
					
						Y = rChain.variable();
						ell = rChain.length() + 1;
					}
				}
			}
			
			//done one right step
			T.push(new Command(Y, ell, Command.RIGHT_DIRECTION));
			
			//do maximal left step (can be zero) and one up step
			Y = R(Y, ell);
			Integer k = H(Y);
			
			//maximal left step plus up step
			if(k.intValue() > -1) {
				T.push(new Command(Y, k, Command.LEFT_DIRECTION));
				T.push(new Command(L(Y, k.intValue()), 0, Command.UP_DIRECTION));
			} else  //just one up step
				T.push(new Command(Y, 0, Command.UP_DIRECTION));
			
			currentNode += ".2";
			return;
		}
	}
	
	/** Navigate to the father node of the current node. */
	public void gotoFatherNode() {
		//delete U-Step
		Command top = T.pop();
		
		//check for grammar root
		if(T.peek().equals(S, H(S), Command.LEFT_DIRECTION)) {
			T.push(top);
			return;
		}
		
		//delete left chain if existent
		if(T.peek().direction().intValue() == Command.LEFT_DIRECTION) 
			T.pop();
		
		//if next top stack is an U-step, we have found the father
		Command rChain = T.pop();
		if(rChain.direction().intValue() == Command.UP_DIRECTION) {
			T.push(rChain);
			
			currentNode = currentNode.substring(0, currentNode.lastIndexOf("."));
			return;
		}
		
		//else the next top stack must be a right chain
		Integer Y = rChain.variable();
		//so decrement if possible
		if(rChain.length().intValue() > 0) {
			T.push(new Command(rChain.variable(), rChain.length()-1, rChain.direction()));
			Y = R(rChain.variable(), rChain.length()-1);
		}
		
		//do one left step (or increment if left chain already exists)
		Integer ell = 0;
		if(!T.isEmpty()) {
			if(T.peek().direction().intValue() == Command.LEFT_DIRECTION) {
				Y = T.peek().variable();
				ell = T.pop().length()+1;
			}
		}
		T.push(new Command(Y, ell, Command.LEFT_DIRECTION));
		Y = L(Y, ell);
		
		//do maximum right chain
		if(W(Y) > -1) {
			T.push(new Command(Y, W(Y), Command.RIGHT_DIRECTION));
			Y = R(Y, W(Y));
		}
		
		//and one U-step
		T.push(new Command(Y, 0, Command.UP_DIRECTION));
		
		currentNode = currentNode.substring(0, currentNode.lastIndexOf("."));
	}
	
	/** Access to the j-th element of the left derivations of non-terminal A_i. */
	private Integer L(int i, int j) {
		return L[i].get(j);
	}

	/** Length of the left derivations of non-terminal A_i.
	    The size is -1 iff A_i is a type-2-nonterminal. Otherwise it is &gt; 0.  
	*/
	private Integer H(int i) {
		return L[i].size() - 1;
	}

	/** Access to the j-th element of the right derivations of non-terminal A_i. */
	private Integer R(int i, int j) {
		return R[i].get(j);
	}

	/** Length of the right derivations of non-terminal A_i. */
	private Integer W(int i) {
		return R[i].size() - 1;
	}
	
	/** Returns true if debug mode is set. */
	public boolean debugMode() {
		return DEBUG_MODE;
	}

	/** Returns informations about the current node. */
	public String getNodeLabel() {
		if(T.isEmpty())
			return "Error: no tree found.";
		
		Rule r = gr.getRule(T.peek().variable());
		
		return
			"current node is "+
			(currentNode.equals("0") ? currentNode : currentNode.substring(2)) + "\n\n" +
			"label: "+ r.label() + "\n"+
			"childrens: " + r.childs() + "\n";
	}

	/** Get debug informations. */
	public String getDebugText() {
		if(DEBUG_MODE) {
			return
				"<html><body>"+
				"Grammar has " +gr.size() + " rules.<br />"+
				"Stack T = " + T.toString() + " with rule A_" +
				T.peek().variable() + " -> " +
				gr.getRule(T.peek().variable()).toString() +
				"</body></html>";
		}
		return "";
	}
	
	/** Resets the stack to "factory settings". */
	public void resetStack() {
		T.clear();
		T.push(new Command(S, H(S), Command.LEFT_DIRECTION));
		T.push(new Command(L(S, H(S)), 0, Command.UP_DIRECTION));
		currentNode = "0";
		
		if(DEBUG_MODE)
			System.out.print("Stack resetted..\n");
	}

}